package 动态规划;

public class 机器人走网格 {
    /**
     *  https://www.hello-algo.com/chapter_dynamic_programming/dp_solution_pipeline/#1432
     *
     *  给定一个 n x m 的二维网格 grid，网格中的每个单元格包含一个非负整数，表示该单元格的代价。
     *  机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。
     *  请返回从左上角到右下角的最小路径和。
     *
     *  题目要求从左上到右下机器人能走的最小路径和，虽然指明了一个路线方向是从左上到右下，但是反过来从右下到左上解题也行
     *
     *  我们先看怎么从左上到右下解题：
     *  要到达 grid[i][j] ， 只能从 grid[i-1][j] 往下移动一行，或者从 grid[i][j-1] 往右移动一列  （i表示行，j表示列）
     *
     *  8*8的 grid 类似如下的表格
     *
     *  0 1 2 3 4 5 6 7
     *  1
     *  2
     *  3
     *  4
     *  5
     *  6
     *  7            i,j
     *
     *  要求最小路径和，那必须是要选择从 grid[i][j] 附近两个路径和最小的点出发到 grid[i][j] 才行，因此得到 grid[i][j] = min (grid[i-1][j],  grid[i][j-1]) + cost[i][j]
     *
     *  因此得到状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
     *
     *  推导出状态转移方程之后，我们要继续思考怎么使用它，数据写入的方式是遍历数组？还是其他操作，边界条件是什么
     */

    /* 最小路径和：动态规划 */
    static int minPathSumDP(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;

        // 有了状态转移方程之后，先把最小子问题的解穷举出来
        int[][] dp = new int[n][m];
        dp[0][0] = grid[0][0];

        for (int j = 1; j < m; j++) {
            // 先把第一行的解穷举出来
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }

        for (int i = 1; i < n; i++) {
            // 再把第一列的解穷举出来
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }

        // 然后从第2行第2列开始使用状态转移方程穷举 dp[i][j] 的解
        for (int i=1; i < n; i++) {
            for (int j=1; j < m; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }

        return dp[n-1][m-1];
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{
                {1,3,1,5},
                {2,2,4,2},
                {5,3,2,1},
                {4,3,5,2},
        };
        System.out.println(minPathSumDP(grid));
    }
}
